On Mice and Coins
The following problem was sent to me by Joel Lewis.
You have 12 mice, one of which eats faster than all the others. You need to find it. You have a supply of standard cupcakes that you value very much and want to minimize how many of them you have to use. The only way you can find the mouse is to give cupcakes to several groups of mice and see which group is the fastest.
We assume that mice chew at a constant speed and all the mice in one group can attack the cake at the same time. I love this puzzle because I love coin problems. Let me restate the puzzle as a coin problem:
You have 12 coins, one of which is fake and weighs less than all the others. You have a balance scale with multiple pans, that is you can weigh several things at once and order them by weight. You do not care about the total number of weighings as in most classical coin puzzles, instead, this time using a pan is expensive and you want to find the fake coin with as few pan-uses as possible.
Spoiler warning: below I will discuss the solution for n mice.
You can, of course, give a cake to every mouse and see which one finishes first. You can save one cake by giving cakes at the same time to all but one of the mice. If everyone finishes simultaneously, the faster mouse is the unfed one.
It wastes cakes to give them to unequally-sized groups of mice. We can do better by copying the classical way to find a fake coin with the minimum number of weighings. That is, for each test, divide the mice into three groups as evenly as possible and give a cake to each of two equally-sized groups. The number of cakes you use is about 2log3n.
I wouldn’t have written this essay if that was the solution. Sometimes you can do even better. For example, you can find the faster mouse out of 12 using only 5 cakes.
First, if you give out k cakes in one test, the test tells you which of k+1 groups the mouse is in. In the worst case, the faster mouse will be in the biggest group, so you should minimize the biggest group. Hence, your groups that get cakes should have ⌈n/(k+1)⌉ mice.
A test with one cake gives no information. I argue that giving out more than three cakes doesn’t gain anything. Indeed, suppose we use four cakes in a test. That is, we divide the mice into five groups A, B, C, D and E, of which the first four are the same size. We can simulate the test by two tests in each of which we give out two cakes. In the first test we give cakes to A+B and C+D. If one of the groups is faster, say A+B, then in the second test give cakes to A and B; if not, E has the faster mouse. I leave it as an exercise to simulate a test with more than four cakes.
Thus, in an optimal strategy we can use two or three cakes per test. Also, if you give one test with k − 1 cakes and the next one with m − 1 cakes, you can switch them with the same effect. The largest group after either order of tests will have at most ⌈n/km⌉ mice.
I don’t need two tests of three cakes each, which would give me a group of size at least ⌈n/16⌉. I can achieve the same result with three tests of two cakes each, with the faster mouse restricted to a group of size at most ⌈n/27⌉.
That means all my tests use two cakes, except I might use three cakes once. It doesn’t matter in what order I conduct the tests, so I can wait until the end to use three cakes. I leave it as an exercise to the reader that the only small number of mice for which we would prefer three cakes is four. From this it follows quickly that for numbers of mice between 3 * 3i + 1 and 4 * 3i, the number of cakes is 2i + 1. For numbers between 4 * 3i + 1 and 3i+2 the answer is 2i + 2.
Share:
Austin:
Hi, Tanya, what if you find a stopwatch in your pocket? Is your strategy still the same?
20 May 2010, 9:41 pmTanya Khovanova:
Austin,
With a stopwatch it is a completely different problem.
20 May 2010, 10:34 pmcolorblind:
Alternate solution 1: Cut *one* cupcake into n pieces. Give a piece to each one of the n mice. The first to finish is your desired mouse.
Alternate solution 2: Pick the fat one. It’s doubtful the fast one stops eating once he’s had his share.
Alternate solution 3: Ask. A fantasy world with standard cupcakes may also have talking mice.
Alternate solution 4: Find a friend. Get them to give you their cupcakes …
22 May 2010, 11:55 amAlexander Bogomolny:
Tanya, hi.
This week I came across your blog and this problem. I am presently with my relatives, the Zbarskys of Rockville, MD. The fellows came up with several ideas. First, there is an implicit assumption that the cupcakes consumption is uniform for all mice but one. Focusing on cupcakes, this can be interpreted as the uniform progress of cupcake disappearance once the mice have applied themselves to the food. The progress can be observed and a judgement passed whether two groups of mice progress with the same speed or not. If that is acceptable, then it may be not necessary to wait until a cupcake has disappeared in its entirety. The implication of this observation is that the cupcakes can be reused. For example, starting with three groups of 3 mice and 3 cupcakes, if the progress on all three cupcakes is the same, you can stop the competition midway ad then give any two cupcakes to the a pair of mice out of the remaining three. If the progress is not uniform, you still have time to stop the competition with two unfinished cupcakes of equal size. So it appears that 3 cupcakes will suffice to determine the fast eater.
They went further and posed a problem with 12 mice of which 2 eat faster than the rest. I missed the proposed solution but the answer they came up with was 6 cupcakes.
23 May 2010, 11:37 pmJBL:
Apologies in advance for the complaining in this paragraph: As with most puzzles of this form, the story of the question is given in natural language and so is subject to vagueness and “clever” solutions that circumvent the intent of the question. However, in this case Tanya has helpfully provided a second story to complement the first, and the nature of this second story indicates that the “clever” approaches you suggest are not what this problem is about. In other words, there is a precise and meaningful mathematical question here, and it seems a little odd to interact with this question primarily as a linguistic riddle in which the actual question is designed to be circumvented, rather than addressed directly. (That said, colorblind’s suggestion number 3 did make me laugh out loud.)
Alexander: yes, one can generalize this question to finding m faster mice among n; in fact, any “traditional” coin puzzle (n coins, of which some number m are known to be heavier, or lighter, or just not of the same weight (but not necessarily known to be heavier or lighter in advance); or questions like https://blog.tanyakhovanova.com/?p=148 , https://blog.tanyakhovanova.com/?p=179 or https://blog.tanyakhovanova.com/?p=217 (in alternate form, “what is the minimal number of weighings necessary?”)) can be rephrased in this context (asking for us to minimize the number of pans used rather than the number of weighings) — thus, every two-pan balance question has a “twin” question with a multi-pan balance (or, equivalently, with mice and cupcakes). It is this situation that made me attracted to the question in the first place.
By the way, if you happen to rediscover the solution for 12 and 2, it seems to me that it would be worth posting here.
11 June 2010, 9:47 amcolorblind:
JBL is correct. With regard to the mice problem, responses 3 & 4 are clearly meant only as joke responses. (A vice I am cursed by…)
Response 1 and 2 seem to work in the mice/cupcake universe but not the coin universe of course.
Notation: m = (x, y) where m is the most required weighings to solve the problem of a group x coins containing y heavier coins.
(12, 2) does have a solution in 5. Split the 12 into 4 groups of 3. Weigh group 1 vs. 2, 2 vs 3, and 3 vs 4. Either 1 or 2 of the 4 groups can be isolated as having heavier coins. Now there are needed at most (3,1) + (3, 1) = 2 additional weighings for the identified heavier groups.
I’m going to assert my (12, 2) solution is optimal and ask if anyone has the solution for the next step, (12,3).
If that’s too easy, here’s a variation to chew on: Let’s say your job is to take groups of 12 coins, all of which have exactly y heavier coins, and pick out those n heavier coins. What method will allow you to do your job the fastest? For example, in the above solution, there are instances where only m-1 weighings would be needed. Is it possible that a algorithm for which at most m+1 weighings might be needed would on average be faster than a solution for which only at most m weighings might be needed for some y?
11 June 2010, 5:35 pmChrist Schlacta:
Address the coins: create 3 stacks of four, and weigh two of them. if they’re equal, then the third stack is the lighter, and has the fake coin. 2 pans used. take three additional pans, and weigh three of the four remaining coins. if they’re equal, the fourth is the lightest. 3 pans used. a total of 5 pans. to mitigate the cost, you pay the pan man with the fake coin?
8 January 2011, 6:03 pmAlkis Piskas:
I’m sorry to come in that late again, but I’m reading the blog archive from bottom up (date wise) and quite irregularily.
Again, I didn’t see a straight answer to the problem, although I found colorblind’s solutions wuite exotic and entertaining!
Well, to avoid more mices eating from a same cake and that sort of variations, plus I don’t like mices at all, I take the coin version as set by Tanya, since I also love coin problems …
I found that the lighter coin can be found with a minimun of 3 weighings, which involves 6 pans:
Put 4 coins in one pan and 4 coins in another pan.
1) The pans balance: The coin is in the 4 coins remaining outside.
Put 2 of them in one pan and the other 2 ones in another pan.
1a) Take the 2 coins that weigh less and weigh them against each other ot find which is the lighter one.
And, if we want to generalize, based on this kind of thinking and using min 2 pans, we find that for:
23 December 2013, 5:45 amn=2-3, 1 weighing is needed
n=4-7 -> 2 weighings are needed
n=8-15 -> 3 weighings are needed
…
That is, with k min weighings, we can find a lighter coin among n = 2^k to 2^(k+1)-1 coins.
Alkis Piskas:
Correction: Back to 12 coins … it involves 2 pans (not 6). All cases involve 2 pans.
And I will be thrilled if someone comes with less weighings! (With coins, please. No mice!)
23 December 2013, 5:57 am